An encoding method using an LDPC code has recently attracted attention. The LDPC code has a parity check matrix H of which most of elements are ‘0,’ and was proposed as a liner block code of low density by Gallager in 1962. However, the LDPC code could not have been realized due to its complexity by the technology at the time when the LDPC code had been proposed. As the LDPC code has been rediscovered in 1995 and its excellent performance has been proved, its studies have been actively made. (References: [1] Robert G. Gallager, “Low-Density Parity-Check Codes”, The MIT Press, Sep. 15, 1963. [2] D. J. C. Mackay, Good error-correcting codes based on very sparse matrices, IEEE Trans. Inform. Theory, IT-45, pp. 399-431 (1999))
An encoding method using an LDPC code will be described as below. In a general LDPC encoding method, a generation matrix G is introduced from an LDPC parity check matrix H to encode an information bit. In order to introduce the generation matrix G, [PT:I] is obtained by Gaussian Reduction of the LDPC parity check matrix H. Supposing that the number of information bits is k and the bit size of a codeword is n, the matrix P has a row size of k and a column size of n-k, and the matrix I is an identity matrix having a row size of k and a column size of k. Supposing that the matrix H is expressed as [PT:I], the matrix G becomes [I:P]. Supposing that an information matrix indicating the information bit of k bit to be encoded is x (matix having a row size of 1 and a column size of k), the encoded codeword c is as follows.c=xG=[x:xP]
A decoding method using an LDPC code will be described as below. In a decoding block of a receiving terminal, the information bit x is obtained from the codeword c by using cHT=0, wherein the codeword c results from decoding of a transmitting terminal. In other words, supposing that the received codeword is c′, a value of c′HT is calculated. As a result, if the resultant value of c′HT is 0, first k bits of c′ are determined as the decoded information bits. If the resultant value of c′HT is not 0, c′ of which c′HT satisfies 0 is found by using a sum-product algorithm through a graph, a belief propagation algorithm, and so on, so as to recover x.
FIG. 1 illustrates a bipartite graph used in a decoding process using an LDPC code. Referring to FIG. 1, it is noted how a multivariable global function is factorized by the product of local functions. The bipartite graph includes a check node for parity check and a variable node representing information word symbol or codeword symbol. The decoding process using a decoding algorithm on the bipartite graph includes the following three unit process steps:
1) first step: update of probability value from a check node to a variable node (check-to-variable βi,j): βi,j is a probability value updated from the ith check node to the jth variable node;
2) second step: update of probability value from a variable node to a check node (variable-to-check αi,j): αi,j is a probability value updated from the ith variable node to the jth check node; and
3) third step: determination of a decoding value through probability of a variable node.
The decoding process using the LDPC code in a receiving party includes determining a value obtained by the equation c·HT=0 as the decoded value if c·HT=0 is satisfied in the third step after the first step and the second step, and iterates the first step and the second step until a given end condition is satisfied if c·HT=0 is not satisfied. The probability value update process in the first step and the second step is performed in such a manner that each update process is iterated by the number of ‘1’ belonging to each row or column of the parity check matrix. As the update process in the first step and the second step is iterated, reliability of the probability value between the check node and the variable node is improved, and, as a result, the probability value is approximated to a true value of the codeword to be obtained. In this case, a ratio between a probability p0 of a specific bit ‘0’ of received information and a probability p1 of a specific bit ‘1’ thereof may be expressed by using log. Such a ratio is referred to as a log-likelihood ratio (LLR) expressed by the following equation 1.LLR=Λ(p0,p1)=ln(p0/p1)  [Equation 1]
For example, if the first step and the second step are applied to a belief propagation algorithm, which is well known, by using the log-likelihood ratio, the following equations 2 and 3 can be obtained. In other words, two input messages (Λ1, Λ2) mean that CHK(Λ1, Λ2) in the equation 2 are probability values updated from the check node to the variable node while VAR(Λ1, Λ2) in the equation 3 are probability values updated from the variable node to the check node.
                                                                        CHK                ⁡                                  (                                                            Λ                      1                                        ,                                          Λ                      2                                                        )                                            =                            ⁢                                                ln                  ⁡                                      (                                          cosh                      ⁡                                              (                                                                              (                                                                                          Λ                                1                                                            +                                                              Λ                                2                                                                                      )                                                    /                          2                                                )                                                              )                                                  -                                                                                                      ⁢                              ln                (                                  cosh                  ⁡                                      (                                          (                                                                        Λ                          1                                                -                                                                              Λ                            2                                                    /                          2                                                                    )                                        )                                                                                                                          =                            ⁢                              2                ⁢                                                      tanh                                          -                      1                                                        ⁡                                      (                                                                  tanh                        ⁡                                                  (                                                                                    Λ                              1                                                        /                            2                                                    )                                                                    ·                                              tanh                        ⁡                                                  (                                                                                    Λ                              2                                                        /                            2                                                    )                                                                                      )                                                                                                          [                  Equation          ⁢                                          ⁢          2                ]            VAR(Λ1,Λ2)=Λ1+Λ2  [Equation 3]
As described above, although proper performance can be obtained by the BP algorithm, if ln(cos h( )) function or tan h( ) function is used as it is, a problem relating to complicated calculation is caused. Accordingly, in practical algorithm, values of ln(cos h( )) function or tan h( ) function are stored using a look-up table and then required values are read out during the next calculation. As a method for reducing a required memory without using a look-up table, there is a min-sum algorithm which is a representative approximation function. The min-sum algorithm obtains the following equation 4 by using a property where the function ln(cosh(x) is converged into |x|−ln2 in the range of x>>1.CHK(Λ1,Λ2)≈|(Λ1+Λ2)/2|−|(Λ1−Λ2)/2|=sgn(Λ1)sgn(Λ2)min(|Λ1|,|Λ2|)  [Equation 4]
Since the min-sum algorithm according to the equation 4 requires simple comparison calculation and message code check calculation, a look-up table for calculation is not required, and very fast calculation can be performed. FIG. 2 illustrates a comparison result between an ideal function value and a function value obtained by the conventional min-sum algorithm.
Various methods are used to realize a decoder using the aforementioned LDPC code. Examples of the methods include using an approximation equation and using a look-up table on a memory. If the look-up table is used to realize a decoder, a problem occurs in that more memories are required to obtain a more precise approximation value.
In case of the conventional min-sum algorithm which approximates a linear function without using the look-up table, |x|−ln2 is used for the whole range so that an approximate value may be obtained in the range of 1<<|x|. However, a problem occurs in that a considerable error occurs if a value of |x| is near to 1 or within the range of 1 as shown in FIG. 2.
FIG. 3 to FIG. 5 illustrate another conventional art that can solve the above problem. The conventional art was filed and registered with the Korean Intellectual Property Office by the applicant of the present invention (Korean Patent Application No. 10-2002-0034987).
Referring to FIG. 3 to FIG. 5, the whole variable range is divided into a plurality of ranges so that a linear function, which can approximate to a nonlinear function, may be selected for each range in order to obtain a function value, whereby the problem of the conventional art can be solved, in which a considerable error occurs when the value of |x| is near to 1 or within the range of 1. In FIG. 3 to FIG. 5, a linear function |x|−ln2 is used in a range where an absolute value of the variable is great while a linear function whose constant value or slope is not 1 is used in the other ranges as a linear function for approximating to the nonlinear function.
In FIG. 4, a linear function 0.40625|x| is used in a range of |x|<1.185. In FIG. 6, a linear function 0.71875(|x|—0.404)+0.398 is used in a range of 0.404<|x|<1.602. Thus, such linear functions are approximated to the original non-linear function ln(cosh(x)), so that the maximum error from the original function may be reduced. In this case, although better performance can be obtained in comparison with the min-sum algorithm, multiplication is required in the process of obtaining the function values because the slope is not 1. For this reason, a problem occurs in that complexity and calculation amount increase.
Meanwhile, for recent LDPC encoding, a method for encoding input data by using the parity check matrix H without using the generation matrix G is generally used. Accordingly, the parity check matrix H may be the most important factor in the encoding method using an LDPC code, as described above. Since the parity check matrix H has a size more than 1000×2000, problems occur in that the parity check matrix H requires much calculation in the encoding and decoding processes, is accompanied with complexity in its application, and requires a lot of storage areas.